//
// Created by 谢祥平 on 22-10-1.
//

#ifndef CARP_LINKLIST_H
#define CARP_LINKLIST_H

#include <bits/stdc++.h>

typedef struct LNode {
    int date;
    struct LNode *next;
} *LinkList;


/**
 * 初始化单链表
 * @param L
 * @return 是否成功
 */
bool initList(LinkList &L) {
    L = (LNode *) malloc(sizeof(LNode));
    L->date = -1;
    L->next = NULL;
    if(L == NULL) {
        return false;
    }
    return true;
}

/**
 * 头插法添加数据
 * @param L
 * @return
 */
LinkList listHeadInsert(LinkList &L) {

    LNode *s;
    int x;
    scanf("%d", &x);

    while (x != 999) {
        s = (LNode *) malloc(sizeof(LNode));
        s->next = L->next;
        L->next = s;
        s->date = x;
        scanf("%d", &x);
    }

    return L;
}

/**
 * 尾插法添加数据
 * @param L
 * @return
 */
LinkList listTailInsert(LinkList &L) {
    LNode *s, *r = L;
    while (r->next != NULL) {
        r = r->next;
    }

    int x;
    scanf("%d", &x);

    while (x != 999) {
        s = (LNode *) malloc(sizeof(LNode));
        r->next = s;
        s->date = x;
        s->next =NULL;
        r = s;
        scanf("%d", &x);
    }

    r->next = NULL;

    return L;
}

/**
 * 按序号查找结点值
 * @param L
 * @param x
 * @return
 */
LNode *getElem(LinkList L, int i) {
    if(L->next == NULL || i == 0)
        return NULL;

    int j = 0;
    LNode *p = L;

    while(p != NULL && j < i) {
        p = p->next;
        ++j;
    }

    return p;
}

/**
 * 按值查找结点
 * @param L
 * @param e
 * @return
 */
LNode *locateElem(LinkList L, int e) {
    if(L->next == NULL)
        return NULL;

    LNode *p = L;

    while (p != NULL && p->date != e)
        p = p->next;

    return p;
}

/**
 * 插入结点
 * @param L
 * @param e
 * @return
 */
bool insertElem(LinkList L, int i, int e) {

    if(i <= 0) {
        return false;
    }

    LNode *p = getElem(L, i-1);
    if(p == NULL)
        return false;

    LNode *s = (LNode *) malloc(sizeof(LNode));
    if(s == NULL)
        return false;
    s->next = p->next;
    s->date = e;
    p->next = s;
    return true;
}

/**
 * 删除结点
 * @param L
 * @param i
 * @return
 */
bool deletElem(LinkList L, int i) {
    LNode *p = getElem(L, i-1);
    if(p == NULL || p->next == NULL)
        return false;

    LNode *q = p->next;
    p->next = q->next;
    free(q);
    return true;
}

/**
 * 求表长
 * @param L
 * @return
 */
int length(LinkList L) {
    if(L->next == NULL || L == NULL)
        return 0;

    int i = 0;
    LNode *p = L->next;
    while(p != NULL) {
        p = p->next;
        i++;
    }

    return i;
}

#endif //CARP_LINKLIST_H